package h0706;

//并查集实现
public class UnionFindSet {
    //祖先. fa[i]=a,表示i的祖先是a
    int[] fa;

    //可以再来一个数据结构记录每棵树的深度，优化合并操作

    //初始化.每个元素的祖先是他自己。
    public UnionFindSet(int n) {
        this.fa = new int[n];
        for (int i = 0; i < n; i++) {
            fa[i] = i;
        }
    }

    //查找x的祖先，并返回。
    public int findParent(int x) {
        if (x == fa[x]) {
            return x;
        }
        //路径压缩。找到祖先的祖先
        return fa[x] = findParent(fa[x]);
    }

    public void union(int x, int y) {
        int a = findParent(x);
        int b = findParent(y);
        if (a != b) {
            this.fa[a] = b;
        }
    }
}
